package 典型.回溯法;

import java.util.ArrayList;
import java.util.List;

// N皇后 https://leetcode-cn.com/problems/n-queens/
public class LC51 {
    public List<List<String>> solveNQueens(int n) {
        //判断边界条件
        if(n<=0) return null;
        //新建一个全局变量保存结果
        List<List<String>> res = new ArrayList<>();
        //保存每一个皇后的位置的结果的变量
        int [] queen = new int [n] ;
        //进行递归
        backTrack(res,queen, 0);
        return res;
    }
    /**
     *pos表示每一行的queen的位置
     *
     **/
    public void backTrack(List<List<String>> res,int[] queen ,int pos){
        if(pos==queen.length){
            List<String> list = new ArrayList<>();
            for(int i=0;i<queen.length;i++){
                //sb表示每一行的符合条件的结果
                StringBuilder sb = drawPoint(queen.length);
                sb.setCharAt(queen[i],'Q');
                list.add(sb.toString());
            }
            res.add(list);
            return ;
        }
        for(int i=0;i<queen.length;i++){
            //循环调用从第一行开始寻找符合条件的皇后位置
            queen[pos]=i;
            //满足条件则开始下一行的寻找不满足的话则返回调整第一行的位置以此来进行回溯
            if(isValid(queen,pos)){
                backTrack(res,queen,pos+1);
            }
        }
    }
    public boolean isValid(int[]queen,int pos){
        for(int i = 0;i<pos;i++){
            if(queen[pos]==queen[i]) return false;
            if(Math.abs(queen[pos]-queen[i])==Math.abs(i-pos)) return false;
        }
        return true;
    }
    public StringBuilder drawPoint(int n){
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ;i<n ; i++) sb.append('.');
        return sb;
    }

}
